package binary_tree.leetcode;

/**
 * 找两个结点的最近公共祖先
 * @Author Stark
 * @Date 2022/3/1 21:29
 */
public class Num236_lowestCommonAncestor {
//    //方法一
//    //用于更新公共祖先
//    private TreeNode lca;
//
//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        findNode(root, p, q);
//        return lca;
//    }
//
//    private boolean findNode(TreeNode root, TreeNode p, TreeNode q) {
//        //走到空,没有找到,返回假
//        if (root == null) {
//            return false;
//        }
//        //递归判断该结点的左子树中是否存在p或q结点
//        int left = findNode(root.left, p, q) ? 1 : 0;
//        //判断右子树中是否存在p或q结点
//        int right = findNode(root.right, p, q) ? 1 : 0;
//        //判断结点本身是否是p或q结点
//        int mid = (root == p || root == q) ? 1 : 0;
//        //在递归过程中,如果有两个值为1,说明就找到了公共最近祖先,更新lca的指向
//        if (left + right + mid == 2) {
//            lca = root;
//        }
//        //递归的返回值来源
//        // 用于判断该结点包括本身,左子树和右子树中是否有一个包含p或者q结点
//        return (left + right + mid) > 0;
//    }

    //方法二
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //如果root为空或者root是p或q中其中一个就返回root
        if(root == null || root == p || root == q){
            return root;
        }
        //在左子树中递归找是否有p或q结点
        //注意:这里递归的返回值不为null就是p或q其中一个
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        //在右子树中递归找是否p或q结点
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        //如果左子树没有,就返回右子树的结果,右子树的结果也可能为空
        if(left == null){
            return right;
        }
        //如果右子树没有,就返回左子树的结果
        if(right == null){
            return left;
        }
        //走到这里说明结点left和right和都不为空
        //所以p和q结点在root的左右子树中,就返回root,即就是最近公共祖先
        return root;
    }
}
